package algorithm;

import com.sun.xml.internal.ws.policy.privateutil.PolicyUtils;

import javax.swing.tree.TreeNode;
import java.util.*;
import java.util.stream.Collectors;

public class BinarySearch {

    public static int loopSearch(int[] nums, int target) {
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                index = i;
            }
        }
        return index;
    }

    public static int binarySearch(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return -1;
    }

    public static int binarySearch2(int[] nums, int target) {
        int i = 0;
        int j = nums.length;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                j = m;
            }
        }
        return -1;
    }

    public static int searchInsert(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }

    public static int loopMySqrt(int x) {
        if (x == 1) {
            return 1;
        }
        int result = 0;
        for (int i = 0; i < x; i++) {
            int sum = i * i;
            //大于int 最大值
            if (sum < 0) {
                return i - 1;
            }
            if (sum == x) {
                return i;
            } else if (sum > x) {
                return i - 1;
            } else if (sum == (x - 1)) {
                result = i;
            }
        }
        return result;
    }

    public static int binarySearchMySqrt(int x) {
        if (x == 0) {
            return x;
        }
        if (x == 1) {
            return x;
        }
        int i = 0;
        int j = x;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (m == x / m) {
                return m;
            } else if (m < x / m) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return j;
    }

    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }

    /**
     * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
     * 循环遍历
     * @param nums
     * @return
     */
    public static int loopMissingNumber(int[] nums) {
        int[] ints = Arrays.stream(nums).sorted().toArray();
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] != i) {
                return i;
            }
        }
        return ints.length;
    }

    /**
     * 二分查找
     * @param nums
     * @return
     */
    public static int binaryMissingNumber(int[] nums) {
        int[] ints = Arrays.stream(nums).sorted().toArray();
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (m == ints[m]) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }

    /**
     * 数组hash
     * @param nums
     * @return
     */
    public static int hashMissingNumber(int[] nums) {
        int n = nums.length;
        Boolean[] booleans = new Boolean[nums.length + 1];
        for (int i = 0; i < n; i++) {
            booleans[nums[i]] = true;
        }
        for (int i = 0; i < booleans.length ; i++) {
            if (booleans[i] == null) {
                return i;
            }
        }
        return n;
    }

    /**
     * 给定两个数组 nums1 和 nums2 ，返回它们的交集输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list1 = Arrays.stream(nums1)
                .boxed()
                .collect(Collectors.toList());
        List<Integer> list2 = Arrays.stream(nums2)
                .boxed()
                .collect(Collectors.toList());
        if (list1.size() > list2.size()){
            list1.retainAll(list2);
            return list1.stream().distinct().mapToInt(Integer::intValue).toArray();
        }else {
            list2.retainAll(list1);
            return list2.stream().distinct().mapToInt(Integer::intValue).toArray();
        }
    }

    public int[] sortIntersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        Set<Integer> set = new HashSet<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                set.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return set.stream().mapToInt(Integer::intValue).toArray();
    }

    public int[] binarySearchIntersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Set<Integer> set = new HashSet<>();
        for (int target : nums2) {
            if (binarySearch(nums1, target) != -1) {
                set.add(target);
            }
        }
        return set.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 猜数字游戏的规则如下：
     *
     * 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
     * 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
     * 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
     * -1：我选出的数字比你猜的数字小 pick < num
     * 1：我选出的数字比你猜的数字大 pick > num
     * 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
     * 返回我选出的数字。
     * @param n
     * @return
     */
    public int guessNumber(int n) {
        int i = 1;
        int j = n;
        while(guess(j) != 0){
            int m = (i + j ) >>> 1;
            if(guess(m) == 0){
                return m;
            }else if(guess(m) == -1){
                j = m - 1;
            }else{
                i = m + 1 ;
            }
        }
        return j;
    }

    public static Integer guess(Integer n) {
        if (n == 6){
            return 0;
        }else if (n > 6){
            return -1;
        }else {
            return 1;
        }
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

